package com.yoshino.leetcode.interview150.binaryTree;

import java.util.Arrays;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    TreeNode tail = null;

    public static void main(String[] args) {
        new Solution().buildTree(new int[]{9, 3, 15, 20, 7}, new int[]{9, 15, 7, 20, 3});
    }

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == q) {
            // 都为空
            return true;
        }
        if (p == null || q == null || p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        invertNode(root);
        return root;
    }

    private void invertNode(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode left = root.left;
        root.left = root.right;
        root.right = left;
        invertNode(root.left);
        invertNode(root.right);
    }

    public boolean isSymmetric(TreeNode root) {
        return isSameTree2(root.left, root.right);
    }

    private boolean isSameTree2(TreeNode left, TreeNode right) {
        if (left == right) {
            // 都为空
            return true;
        }
        if (left == null || right == null || left.val != right.val) {
            return false;
        }
        // 对称
        return isSameTree2(left.left, right.right) && isSameTree2(left.right, right.left);
    }

    public TreeNode buildTree1(int[] preorder, int[] inorder) {
        // 中序 + 前序：将子树拆为 左右子树； 前序：先遍历根节点
//        if (preorder.length == 0) {
//            return null;
//        }
//        TreeNode root = new TreeNode(preorder[0]);
//        for (int i = 0; i < preorder.length; i++) {
//            if (preorder[0] == inorder[i]) {
//                // 分为左右子树
//                root.left = buildTree(Arrays.copyOfRange(preorder, 1, i + 1), Arrays.copyOfRange(inorder, 0, i));
//                root.right = buildTree(Arrays.copyOfRange(preorder, i + 1, preorder.length), Arrays.copyOfRange(inorder, i + 1, preorder.length));
//                break;
//            }
//        }
//        return root;
        return buildTree(preorder, inorder, 0, preorder.length, 0, inorder.length);
    }

    public TreeNode buildTree(int[] preorder, int[] inorder, int pFrom, int pTo, int iFrom, int iTo) {
        if (pTo - pFrom <= 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[pFrom]);
        if (pTo - pFrom == 1) {
            return root;
        }
        for (int i = iFrom; i < iTo; i++) {
            if (preorder[pFrom] == inorder[i]) {
                // 分为左右子树
                root.left = buildTree(preorder, inorder, pFrom + 1, i - iFrom + pFrom + 1, iFrom, i);
                root.right = buildTree(preorder, inorder, pFrom + 1 + i - iFrom, pTo, i + 1, iTo);
                return root;
            }
        }
        return null;
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // 从后往前找根节点
        if (postorder.length == 0) {
            return new TreeNode();
        }
        int n = postorder.length - 1;
        TreeNode root = new TreeNode(postorder[n]);
        for (int i = n; i >= 0; i--) {
            if (postorder[n] == inorder[i]) {
                root.right = buildTree(Arrays.copyOfRange(inorder, i + 1, inorder.length), Arrays.copyOfRange(postorder, i, n));
                root.left = buildTree(Arrays.copyOfRange(inorder, 0, i), Arrays.copyOfRange(postorder, 0, i));
                return root;
            }
        }
        return null;
    }

    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        if (root.left != null && root.right != null) {
            root.left.next = root.right;
        } else if (root.left != null && root.right == null) {
            // 判断相邻节点
            root.left.next = getNext(root.next);
        }
        if (root.right != null) {
            // 只能拿相邻节点
            root.right.next = getNext(root.next);
        }
        connect(root.right);
        connect(root.left);
        return root;
    }

    private Node getNext(Node next) {
        if (next == null) {
            return null;
        }
        if (next.left != null) {
            return next.left;
        }
        if (next.right != null) {
            return next.right;
        }
        // 是否还有相邻点
        if (next.next != null) {
            return getNext(next.next);
        }
        return null;
    }

    public void flatten(TreeNode root) {
        // 最下层的先处理，最后自身
        if (root == null) {
            return;
        }
        flatten(root.right);
        flatten(root.left);
        root.right = tail;
        root.left = null;
        tail = root;
    }

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        int cur = targetSum - root.val;
        if (cur == 0 && root.left == null && root.right == null) {
            return true;
        }
        // 先序
        return hasPathSum(root.left, cur) || hasPathSum(root.right, cur);
    }

    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return root.val;
        }
        int sum = root.val;
        return sumNumbers(root.left, sum) + sumNumbers(root.right, sum);
    }

    public int sumNumbers(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        int cur = sum * 10 + root.val;
        if (root.left == null && root.right == null) {
            return cur;
        }
        return sumNumbers(root.left, cur) + sumNumbers(root.right, cur);
    }

    int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        /**
         对于任意一个节点, 如果最大和路径包含该节点, 那么只可能是两种情况:
         1. 其左右子树中所构成的和路径值较大的那个加上该节点的值后向父节点回溯构成最大路径
         2. 左右子树都在最大路径中, 加上该节点的值构成了最终的最大路径
         **/
        getMax(root);
        return res;
    }

    private int getMax(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 如果子树路径和为负则应当置0表示最大路径不包含子树
        int left = Math.max(0, getMax(root.left));
        int right = Math.max(0, getMax(root.right));
        // 判断在该节点包含左右子树的路径和是否大于当前最大路径和
        res = Math.max(res, left + right + root.val);
        return Math.max(left, right) + root.val;
    }

    public int countNodes(TreeNode root) {
        // 二分查找 + 位运算
        if (root == null) {
            return 0;
        }
        int level = 0;
        TreeNode cur = root;
        while (cur.left != null) {
            level++;
            cur = cur.left;
        }
        // 节点的个数
        int low = 1 << level, high = (1 << level + 1) - 1;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (exists(root, level, mid)) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }

    private boolean exists(TreeNode root, int level, int k) {
        // 可以往下走的次数
        int bits = 1 << (level - 1);
        TreeNode node = root;
        while (node != null && bits > 0) {
            if ((bits & k) == 0) {
                // 往左走
                node = node.left;
            } else {
                node = node.right;
            }
            bits >>= 1;
        }
        return node != null;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            // 左右子树存在
            return root;
        } else if (left != null) {
            // 当前左子树存在一个点
            return left;
        } else if (right != null) {
            return right;
        }
        return null;
    }
}